package 滑动窗口.无重复最长子串;

import java.util.HashMap;
import java.util.Map;
/**
 * 题目优化
 * 之前遇到重复字符，要一个一个地 remove 左边的字符，移动 left
 * 我们可以用 Map 记录每个字符上一次出现的位置，一步到位把 left 跳过去。
 * */

class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        // 记录每个字符上一次出现的位置
        Map<Character,Integer> lastIndex = new HashMap<>();
        int res = 0;
        int left = 0; // 当前窗口左边界

        for(int right = 0;right < s.length();right++){
            char c = s.charAt(right);

            // 如果 c 出现过，并且上一次的位置在当前窗口内
            if(lastIndex.containsKey(c) && lastIndex.get(c) >= left){
                // 把left移动到上一次c出现位置的下一位
                left = lastIndex.get(c) + 1;
            }
            // 更新c的最新出现位置
            lastIndex.put(c,right);

            // 当前窗口[left,right]的长度
            res = Math.max(res,right - left + 1);
        }
        return res;
    }
}